package com.ljy.algorithm;

import java.util.HashSet;
import java.util.Set;
import java.util.Scanner;

public class DanChunXing {
    static int MAX_COUNT = 20; // 最大迭代次数

    public static void main(String[] args) {
        Main ma = new Main();
        Scanner sc = new Scanner(System.in);
        System.out.println("方程个数");
        int m = sc.nextInt();
        System.out.println("未知量个数");
        int n = sc.nextInt();
        // System.out.println(m+" "+n);
        ma.init(m, n);
        ma.in();
        int i = 0;

        while (true) {
            // ma.visit3();

            while (true) {
                ma.visit3();
                System.out.println("是否需要修改?(输入1则需要，其他数字则不需要)");
                if (sc.nextInt() == 1) {
                    System.out.println("输入1则修改数据，输入2则删除列");
                    switch (sc.nextInt()) {
                    case 1:
                        ma.update();
                        break;
                    case 2:
                        ma.delete();
                        break;
                    default:
                        break;
                    }
                } else break;
            }
            ma = solution(ma, m, n);
        }
    }

    public static Main solution(Main ma, int m, int n) {

        int ib = 0;
        while (true) {
            if (ib++ > MAX_COUNT) {
                System.out.println("已达最大迭代次数");
                break;
            }
            // cj-zj
            ma.cjDelZj();

            // th
            int max = ma.max_index(ma.data[m], 1);
            if (ma.data[m][max] <= 0) {
                System.out.println("结束");
                // ma.visit();
                ma.visit2();
                break;
            } else {
                boolean b = true; // 假设全负
                for (int i = 0; i < m; i++) {
                    if (ma.data[i][max] > 0) {
                        b = false;
                        break;
                    }
                }
                if (b) {
                    System.out.println("无可行解");
                    ma.visit2();
                    break;
                }
                ma.setTh(max);
                ma.visit2();
                // 确定新基变量
                int min = ma.min_index(ma.th);

                System.out.println("{" + ma.xb[min] + "换出,x" + max + "换入}");
                ma.xb[min] = max;
                ma.setXb(ma.xb);
                // min行除以data[min][max]
                ma.data[min] = ma.sub(ma.data[min], ma.data[min][max]);
                // 其他，若data[i][max]不为0，第i行减去min行的data[i][max]倍
                for (int i = 0; i < m; i++) {
                    if (i != min)
                        if (ma.data[i][max] != 0)
                            ma.data[i] = ma.addAndMul(ma.data[i], ma.data[min], -ma.data[i][max]);
                }
                // ma.visit2();
            }
        }
        return ma;
    }
}
class Main {
    double[][] data;//第0列存储b，其他位置x1,x2...x(n);前0到(m-1)行存储约束条件,m行cj-zj
    double[] cj;
    //double[] b;
    double[] th;
    int[] xb;
    double[] cb;
    int m,n;
    // m个方程，n个未知数
    public void init(int m, int n) {
        data = new double[m + 1][n + 1];
        // m+1显示cj-zj，第一行b
        cj = new double[n+1];
        //b = new double[m];
        th=new double[m];
        xb=new int[m];
        cb=new double[m];
        this.m=m;
        this.n=n;
    }
    public void delete() {
        Scanner sc=new Scanner(System.in);

        System.out.println("依次要删除的列(x几就是第几列),输入负数则结束");
        Set<Integer> set=new HashSet<>();
        int i1=0;
        while((i1=sc.nextInt())>=0) {
            set.add(i1);
        }
        int size=set.size();
        //拷贝数据
        int n1=n-size;
        double[][] data1=new double[m + 1][n + 1-size];
        int j1=1;
        for(int i=0; i<m; i++) {
            j1=1;
            for (int j=1; j<n1+1; j++) {
                while(set.contains(j1))j1++;
                data1[i][j]=data[i][j1++];
            }
            data1[i][0]=data[i][0];
        }
        data=data1;
        double[] cj1=new double[n+1-size];
        j1=1;
        for(int i=1; i<n1+1; i++) {
            while(set.contains(j1))j1++;
            cj1[i]=cj[j1++];
        }
        cj=cj1;
        n=n1;

    }
    public void update() {
        System.out.println("输入要修改的内容所对应的代号(##后的第一个数字)");
        Scanner sc=new Scanner(System.in);
        switch (sc.nextInt()) {
        case 2:
            System.out.println("第几个约束条件?");
            int i1=sc.nextInt()-1;
            System.out.println("请依次输入系数");
            for (int j=1; j<n+1; j++) {
                data[i1][j]=sc.nextDouble();
            }
            System.out.println("b"+(1+i1));
            data[i1][0]=sc.nextDouble();
            break;
        case 1:
            System.out.println("请依次输入目标函数的系数");
            for(int i=1; i<n+1; i++) {
                cj[i]=sc.nextDouble();
            }
            break;
        case 3:
            System.out.println("每一行的基变量");
            for(int i=0; i<m; i++) {
                //System.out.print(i+" "+m);
                xb[i]=sc.nextInt();
                cb[i]=cj[xb[i]];
            }
            break;
        }
    }
    public void visit3() { //用于挨个显示数据。
        System.out.println("\n##1 目标函数");
        for(int j=1; j<n+1; j++) {
            if(j==1)System.out.printf("%.3f x%d",cj[j],j);
            else System.out.printf(" + %.3f x%d",cj[j],j);
        }
        System.out.println("\n##2 约束");
        for(int i=0; i<m; i++) {
            for(int j=0; j<n+1; j++) {
                if(j==0) {
                    System.out.printf("%.3f=",data[i][j]);
                } else if(j==1) {
                    System.out.printf("%.3f x%d",data[i][j],j);
                } else {
                    System.out.printf(" + %.3f x%d",data[i][j],j);
                }
            }
            System.out.println();
        }
        System.out.println("##3 基变量");
        for(int i=0; i<m; i++) {
            System.out.print("x"+xb[i]+"  ");
        }
        System.out.println();
    }
    //输出
    public void visit2() {
        String[][]str=new String[m+3][n+4];
        //第0行
        str[0][1]="cj";
        for(int j=3; j<n+3; j++) {
            str[0][j]=String.format("%.2f",cj[j-2]);
        }
        str[0][n+3]="θi";
        //第一行
        str[1][0]="Cb";
        str[1][1]="Xb";
        str[1][2]="b";
        for(int j=3; j<n+3; j++) {
            str[1][j]="x"+(j-2);
        }
        //cb
        for(int i=2; i<m+2; i++) {
            str[i][0]=String.format("%.3f",cb[i-2]);
        }
        //xb
        for(int i=2; i<m+2; i++) {
            str[i][1]=String.format("x%d",xb[i-2]);
        }
        //data
        for(int i=2; i<m+3; i++) {
            for(int j=2; j<n+3; j++) {
                str[i][j]=String.format("%.3f",data[i-2][j-2]);
            }
        }
        //th
        for(int i=2; i<m+2; i++) {
            str[i][n+3]=String.format("%.3f",th[i-2]);
        }
        for(int i=0; i<m+3; i++) {
            for(int j=0; j<n+4; j++) {
                if(str[i][j]==null)
                    System.out.printf("%8s","*");
                else
                    System.out.printf("%8s",str[i][j]);
            }
            System.out.println();
        }
        System.out.println("==========");
    }


    // 输出格式//已弃用
    public void visit() {
        for(int i=0; i<n+1; i++) {
            System.out.print(cj[i]+" ");
        }
        System.out.println();
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[0].length; j++) {
                System.out.print(data[i][j] + " ");
            }
            if(i<th.length) {
                System.out.print(" θ:"+th[i]);
                System.out.print(" Cb:"+cb[i]);
                System.out.print(" X"+xb[i]);
            }
            System.out.println();
        }
        System.out.println("==============");
    }

    //输入数据
    public void in() {
        Scanner sc=new Scanner(System.in);
        System.out.println("约束条件");
        for(int i=0; i<m; i++) {
            System.out.println("约束条件"+(i+1));
            for (int j=1; j<n+1; j++) {
                data[i][j]=sc.nextDouble();
            }
            System.out.println("b"+(1+i));
            data[i][0]=sc.nextDouble();
        }
        System.out.println("目标函数");
        for(int i=1; i<n+1; i++) {
            cj[i]=sc.nextDouble();
        }
        System.out.println("每一行的基变量");
        for(int i=0; i<m; i++) {
            //System.out.print(i+" "+m);
            xb[i]=sc.nextInt();
            cb[i]=cj[xb[i]];
        }
    }
    //cj-zj
    public void cjDelZj() {
        double d=0;
        for(int j=0; j<data[m].length; j++) {
            d=0;
            for(int i=0; i<m; i++) {
                d+=data[i][j]*cb[i];
            }
            data[m][j]=cj[j]-d;
        }
    }
    //th
    public void setTh(int index) {
        for(int i=0; i<m; i++) {
            if(data[i][index]!=0)
                th[i]=data[i][0]/data[i][index];
            else th[i]=0;
        }
    }

//设置基变量
    public void setXb(int [] xb) {
        if(xb.length!=this.xb.length)
            throw new RuntimeException("基变量个数设置出错");
        this.xb=xb;
        for(int i=0; i<m; i++) {
            cb[i]=cj[xb[i]];
        }
    }

    // ds数组除以d后得到的数组,返回ds
    public double[] sub(double[] ds, double d) {
        if (d!=0)
            for (int i = 0; i < ds.length; i++) {
                ds[i] = ds[i] / d;
            } else System.out.println("d=0");
        return ds;
    }
    // ds1加上ds2的d倍，返回ds1
    public double[] addAndMul(double[] ds1, double[] ds2, double d) {
        if (ds1.length != ds2.length) {
            throw new RuntimeException("行变化时长度不同");
        }
        for (int i = 0; i < ds1.length; i++) {
            ds1[i] = ds1[i] + ds2[i] * d;
        }
        return ds1;
    }
    // 返回当前数组最大数字所对应的索引
    public int max_index(double[] ds) {
        return max_index(ds, 0);
    }
    // 从指定位置开始找，返回当前数组最大数字所对应的索引
    public int max_index(double[] ds, int index) {
        int max = index;
        for (int i = index; i < ds.length; i++) {
            if (ds[i] > ds[max]) {
                max = i;
            }
        }
        return max;
    }
    // 返回当前数组最大数字所对应的索引
    public int min_index(double[] ds) {
        return min_index(ds, 0);
    }
    // 从指定位置开始找，返回当前数组最小正数所对应的索引
    public int min_index(double[] ds, int index) {
        int min = 0;
        for (int i = index; i < ds.length; i++) {
            if(ds[i]>0) {
                min=i;
                break ;
            }
        }
        if(ds[min]<=0) {
            throw new RuntimeException("θi均小于0");
        }
        for (int i = index; i < ds.length; i++) {
            if (ds[i] < ds[min]&&ds[i]>0) {
                min = i;
            }
        }
        return min;
    }
}
